package array;

import java.util.*;

/**
 * 给你一个二维字符串数组 responses，其中每个 responses[i] 是一个字符串数组，表示第 i 天调查的回答结果。
 * 请返回在对每个 responses[i] 中的回答 去重 后，所有天数中 最常见 的回答。如果有多个回答出现频率相同，则返回 字典序最小 的那个回答。
 * <p>
 * 示例 1：
 * 输入： responses = [["good","ok","good","ok"],["ok","bad","good","ok","ok"],["good"],["bad"]]
 * 输出： "good"
 * 解释：
 * 每个列表去重后，得到 responses = [["good", "ok"], ["ok", "bad", "good"], ["good"], ["bad"]]。
 * "good" 出现了 3 次，"ok" 出现了 2 次，"bad" 也出现了 2 次。
 * 返回 "good"，因为它出现的频率最高。
 * <p>
 * 示例 2：
 * 输入： responses = [["good","ok","good"],["ok","bad"],["bad","notsure"],["great","good"]]
 * 输出： "bad"
 * 解释：
 * 每个列表去重后，responses = [["good", "ok"], ["ok", "bad"], ["bad", "notsure"], ["great", "good"]]。
 * "bad"、"good" 和 "ok" 都出现了 2 次。
 * 返回 "bad"，因为它在这些最高频率的词中字典序最小。
 *
 * @author Jisheng Huang
 * @version 20250502
 */
public class CommonResponse_3527 {
    /**
     * 把 responses[i] 去重后，用哈希表 cnt 统计每个字符串的出现次数。
     * 统计的过程中，维护最大出现次数 maxCnt 以及字典序最小的答案。
     *
     * @param responses the given list of responses
     * @return the most common string
     */
    public static String findCommonResponse(List<List<String>> responses) {
        String ans = "";
        int maxCnt = 0;
        Map<String, Integer> cnt = new HashMap<>();
        Set<String> vis = new HashSet<>();

        for (List<String> resp : responses) {
            vis.clear();

            for (String s : resp) {
                if (!vis.add(s)) {  // s在vis中
                    continue;
                }

                int c = cnt.merge(s, 1, Integer::sum);  // c = ++cnt[s].

                if (c > maxCnt || c == maxCnt && s.compareTo(ans) < 0) {
                    maxCnt = c;
                    ans = s;
                }
            }
        }

        return ans;
    }

    public static void main(String[] args) {

    }
}
